1. Field of the Invention
The present invention relates generally to feature extracting circuits and, more particularly, to a figure extracting circuit arranged to effect feature extraction on an image by counting direction indices relating to the outline of a binary digital image.
2. Description of the Related Art
Image recognition apparatus of the type used for character recognition, pattern recognition or the like are commonly arranged to perform the process of calculating the "feature amount" of an image. In one known method, the direction of an outline which defines a particular black-pixel component (or area) is detected as the feature amount. An optical character reader (OCR) of the conventional type which employs the known method will be described below.
For example, in the OCR shown in FIG. 2, a document to be recognized is inputted through an image scanner 5 and the resulting digitized image is stored in a RAM 3 by means of an I/O control section 4. Then, a CPU 1 calculates the feature amount of the image stored in the RAM 3 in accordance with the programs stored in a ROM 2. The image stored in the form of a RAM 3 assumes the two-dimensional matrix as shown in FIG. 3. In the matrix of the input image, the X coordinate axis extends from the uppermost left position (as viewed in FIG. 3) to the right in the horizontal direction, while the Y coordinate axis extends from the same position to the bottom in the vertical direction. If the color of a particular read pixel is black, the value "1" is placed at the corresponding pixel position in the matrix, while if the color is white, the value "0" is place at the corresponding pixel position.
After the image has been stored in the RAM 3, the CPU 1 effects a filtering process. The filtering process means a process for removing noise from an image input by the image scanner 5, a process for correcting, as shown in FIG. 4, a portion 31 which includes the part of an outline which was originally smooth but was notched during digitization by the image scanner 5, thereby providing a portion 32 which includes the part thus corrected, or other similar processes.
The algorithm of this filtering process is explained with reference to FIG. 6. In the following explanation, it is assumed that an input image has a width of 63 pixels and a height of 63 pixels and that P (x, y) represents the value of a pixel positioned at coordinates (x, y).
The following process is repeated for each value of y (y=2, 3 . . . , and 62). For x=2 the value of the pixel positioned at coordinates (2, 2) is calculated from the values of eight neighboring pixels by using the following equation. ##EQU1## where P.sub.i (P.sub.0, P.sub.1, . . . , P.sub.8) represents each point shown in FIG. 5; P.sub.0 =P(x, y); P.sub.1 =P(x+1, y); P.sub.2 =P(x+1, y-1); P.sub.3 =P(x, y-1); P.sub.4 =P(x-1, y-1); P.sub.5 =P(x-1, y); P.sub.6 =P(x-1, y+1); P.sub.7 =P(x, y+1); and P.sub.8 =P(x+1, y+1). "//" represents that after dividing by the divisor (0.5, here), the figures to the right of the decimal point are omitted from the quotient. More specifically, of a total of nine pixels, i.e., one particular pixel P(x, y) and eight pixels which neighbor on this pixel, if at least five pixels are black, the pixels assume the same array as that corresponding to Q(x, y).
Once the filtering process is completed, then a direction index is calculated. The direction index is a value which, as shown in FIG. 8, indicates the direction of the boundary between adjacent black and white pixels. As shown by the patterns of FIG. 9, the direction index "0" indicates that the boundary runs in the horizontal direction, index "1" indicates that the boundary is located in the upper right side or the lower left side, the direction index "2" indicates that the boundary runs in the vertical direction, and the direction index "3" indicates that the boundary is located in the lower right side or the upper left side. In other words, the direction index of the pixel P(x, y) is calculated from a total of four pixels, i.e., the three neighboring pixels P(x+1, y), P(x, y+1) and p(x+1, y+1) as well as the pixel P(x, y) of interest.
The feature amount of a character of interest is determined in accordance with how many outline portions indicated by the individual direction indexes "0", "1", "2" and "3" are contained in the character. For example, since the patterns 91 and 92 shown in FIG. 9 each include two outlines, the number of outlines counted needs to be two. For this purpose, added data is obtained which determines whether the number of outlines counted is one or two. Of the patterns shown in FIG. 9, the patterns 91 and 92 each correspond to added data "2", while the other patterns correspond to added data "1". If there is no pattern similar to any of the patterns of FIG. 9, it indicates that no outline is present, and the corresponding added data is set to "0".
An algorithm for calculating such a direction index is explained with reference to the flow charts of FIGS. 10A and 10B. In Step S101, the vertical coordinate y is initialized with "1", and in Step S102 the horizontal coordinate x is initialized with "1". Then, in Step S103, the values Q (1, 1), Q(2, 1), Q(1, 2) and Q(2, 2) of individual coordinates (1, 1), (2, 1), (1, 2) and (2, 2) are read from image data Q to which a filtering process has been applied, and these values Q (1, 1), Q(2, 1), Q(1, 2) and Q(2, 2) are set as Q.sub.1, Q.sub.2, Q.sub.3 and Q.sub.4, respectively.
If Q.sub.1 =1, Q.sub.2 =1, Q.sub.3 =0 and Q.sub.4 =0, the process proceeds from Step S104 to Step S106, where a direction index H (1, 1) is set to 0 with added data D(1, 1) set to 1.
If Q.sub.1 =0, Q.sub.2 =0, Q.sub.3 =1 and Q.sub.4 =1, the process proceeds from Step S105 to Step S106, where a direction index H (1, 1) is set to 0 with added data D(1, 1) set to 1.
If Q.sub.1 =0, Q.sub.2 =1, Q.sub.3 =1 and Q.sub.4 =1, the process proceeds from Step S107 to Step S109, where the direction index H (1, 1) is set to 1 with the added data D(1, 1) set to 1.
If Q.sub.1 =1, Q.sub.2 =1, Q.sub.3 =1 and Q.sub.4 =0, the process proceeds from Step S108 to Step S109, where the direction index H (1, 1) is set to 1 with the added data D(1, 1) set to 1.
If Q.sub.1 =0, Q.sub.2 =1, Q.sub.3 =1 and Q.sub.4 =0, the process proceeds from Step S110 to Step S111, where the direction index H (1, 1) is set to 1 with the added data D(1, 1) set to 2.
If Q.sub.1 =0, Q.sub.2 =1, Q.sub.3 =0 and Q.sub.4 =1, the process proceeds from Step S112 to Step S114, where the direction index H (1, 1) is set to 2 with the added data D(1, 1) set to 1.
If Q.sub.1 =1, Q.sub.2 =0, Q.sub.3 =1 and Q.sub.4 =0, the process proceeds from Step S113 to Step S114, where the direction index H (1, 1) is set to 2 with the added data D(1, 1) set to 1.
If Q.sub.1 =1, Q.sub.2 =0, Q.sub.3 =1 and Q.sub.4 =1, the process proceeds from Step S115 to Step S117, where the direction index H (1, 1) is set to 3 with the added data D(1, 1) set to 1.
If Q.sub.1 =1, Q.sub.2 =1, Q.sub.3 =0 and Q.sub.4 =1, the process proceeds from Step S116 to Step S117, where the direction index H (1, 1) is set to 3 with the added data D(1, 1) set to 1.
If Q.sub.1 =1, Q.sub.2 =0, Q.sub.3 =0 and Q.sub.4 =1, the process proceeds from Step S118 to Step S119, where the direction index H (1, 1) is set to 3 with the added data D(1, 1) set to 2.
If none of the above conditions is satisfied, it indicates that no outline is detected. Accordingly, the process proceeds to Step S120, where the added data D (1, 1) is set to "0".
Then, in Step S121, the value of the horizontal coordinate x is counted up by one and the process returns to Step S103, where the above-described process is performed. This process is repeated until the value of the horizontal coordinate x reaches 62. When 62 is reached, the process proceeds to Step S123, where the value of the vertical coordinate y is counted up by one. Until the value of the vertical coordinate y reaches 62, the process sequentially returns to Step S102, and similar processes are performed with respect to the vertical coordinate y (=2, 3, . . . , 62).
When all these processes have been completed, 62.times.62 direction indexes which consist of H(1, 1), H(2, 1), . . . , H(62, 1), and H(1, 2), . . . , H(62, 62) as well as 62.times.62 pieces of added data which consist of D(1, 1), D(2, 1), . . . , D(62, 1), and D(1, 2), . . . , D(62, 62) are obtained.
In the conventional method described above, however, the program requires several hundred process steps. Accordingly, the calculation time per pixel reaches several hundred .mu.sec. or thereabouts and it is therefore impossible to realize the speeds at which recognition processing is effected in practice.